//https://developer.aliyun.com/article/1128467

//将单向链表按某值划分成左边小、中间相等、右边大的形式
//solution2：利用压节点去实现；

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <set>

using namespace std;

struct Node {
      int value;
      struct Node* next;
      Node(int x) :
            value(x), next(nullptr) {
      }
};

class Solution {

public :
static Node* listPartition2(Node* head, int pivot){
    Node* sH = nullptr;  // small head
    Node* sT = nullptr;  // small tail
    Node* eH = nullptr;  // equal head
    Node* eT = nullptr;  // equal tail
    Node* mH = nullptr;  // big head
    Node* mT = nullptr;  // big tail
    Node* next = nullptr; // save next Node*
    // every Node* distributed to three lists
    while(head != nullptr){
        next = head->next;
        head->next = nullptr;
        if(head->value < pivot){
            if(sH == nullptr){
                sH = head;
                sT = head;
            }else{
                sT->next = head;
                sT = head;
            }
        }else if(head->value == pivot){
            if(eH == nullptr){
                eH = head;
                eT = head;
            }else{
                eT->next = head;
                eT = head;
            }
        }else if(head->value > pivot){
            if(mH == nullptr){
                mH = head;
                mT = head;
            }else{
                mT->next = head;
                mT = head;
            }
        }
        head = next;
    }
    // small and equal reconnect
    if(sT != nullptr){
        sT->next = eH;
        eT = eT == nullptr ? sT : eT; // 下一步，谁去连大于区域的头，谁就变成eT
    }
    // 上面的if，不管跑了没有，et
    // all reconnect
    if(eT != nullptr){        // 如果小于区域和等于区域，不是都没有
        eT->next = mH;
    }
    return sH != nullptr ? sH : (eH != nullptr ? eH : mH);
}
};